package 前缀和;

public class 矩阵区域和8 {
    //二维前缀和
    //https://leetcode.cn/problems/matrix-block-sum/description/
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int w = mat.length, l = mat[0].length;
//        int[][] dp_sum = new int[w + 2][l + 2]; // dp表只对公式里-1会越界 去多给格子 让dp表里对应位置填数据时 公式不会越界地等效算出值
        int[][] dp_sum = new int[w + 1][l + 1]; // dp表只对公式里-1会越界 去多给格子 让dp表里对应位置填数据时 公式不会越界地等效算出值
        for (int i = 1; i < w + 1; i++)
            for (int j = 1; j < l + 1; j++)
                dp_sum[i][j] = dp_sum[i][j - 1] + dp_sum[i - 1][j] - dp_sum[i - 1][j - 1] + mat[i - 1][j - 1];
        int[][] ret = new int[w][l];
        for (int i = 0; i < w; i++) {
            for (int j = 0; j < l; j++) {
                int dp_x1 = Math.max(0,i - k) + 1,
                    dp_y1 = Math.max(0,j - k) + 1,
                    dp_x2 = Math.min(i + k,w - 1) + 1,
                    dp_y2 = Math.min(j + k,l - 1) + 1;
                ret[i][j] = dp_sum[dp_x2][dp_y2] -
                        dp_sum[dp_x1 - 1][dp_y2] -
                        dp_sum[dp_x2][dp_y1 - 1] +
                        dp_sum[dp_x1 - 1][dp_y1 - 1];
            }
        }
        return ret;
    }
}
